package example3;

//238. 除自身以外数组的乘积
public class LeetCode238 {
    public static void main(String[] args) {

    }
}

class Solution238 {
    /**
     * 方法三：双指针，beforeSum表示前缀积，afterSum表示后缀积
     * 这个比前两种方法还慢一些，本质上看上去只遍历了2遍，但其实第二个for中，
     * i从0到n-1，j从n-1到0，本质这个也算两遍，而且每轮循环4个赋值，所以本质还是比前两种方法慢，
     * 不要被一次遍历的表象迷惑了，要看本质
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            answer[i] = 1;
        }
        int beforeSum = 1;
        int afterSum = 1;
        //i从前往后遍历，i的遍历会让每个结果都先得到它左边所有元素的积，
        //j从后往前遍历，j的遍历会让每个结果都得到它右边所有元素的积
        for(int i=0,j=nums.length-1;i<nums.length;i++,j--){
            answer[i] *= beforeSum;
            answer[j] *= afterSum;
            beforeSum *= nums[i];
            afterSum *= nums[j];
        }
        return answer;
    }

    /**
     * 方法二：方法一的优化，同样是时间复杂度 O(n)，但是空间占用比方法一少
     * @param nums
     * @return
     */
    public int[] productExceptSelf2(int[] nums) {
        //dp1表示第i个元素之前所有元素的积，同时在这个方法中也可以作为结果数组
        int[] dp1 = new int[nums.length];
        dp1[0] = 1;
        for(int i=1;i<nums.length;i++){
            dp1[i] = dp1[i-1] * nums[i-1];
        }
        int temp = 1;
        for(int i=nums.length-1;i>=0;i--){
            dp1[i] = dp1[i] * temp;
            temp *= nums[i];
        }
        return dp1;
    }

    /**
     * 方法一：动态规划
     * 用一个dp1记录每个元素前半部分的所有元素的积，另一个dp2记录每个元素后半部分所有元素的积
     * @param nums
     * @return
     */
    public int[] productExceptSelf1(int[] nums) {
        //dp1表示第i个元素之前所有元素的积
        int[] dp1 = new int[nums.length];
        //dp2表示第i个元素之后所有元素的积
        int[] dp2 = new int[nums.length];
        int[] result = new int[nums.length];
        dp1[0] = 1;
        dp2[nums.length - 1] = 1;
        for(int i=1;i<nums.length;i++){
            dp1[i] = dp1[i-1] * nums[i-1];
        }
        for(int i=nums.length-2;i>=0;i--){
            dp2[i] = dp2[i + 1] * nums[i + 1];
            result[i] = dp1[i] * dp2[i];
        }
        result[nums.length-1] = dp1[nums.length-1];
//        for(int i=0;i<nums.length;i++){
//            result[i] = dp1[i] * dp2[i];
//        }
        return result;
    }
}
